/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package my.algorithms.mcorrea;

/**
 * 
 * @author mcorrea
 */
public class BinarySearch {
	
	 
	public static void main(String args[]){
	
		int array[] ={-89,-5, 1, 2, 3, 4, 5, 6 };
		
		int high = array.length - 1;
		int low = 0 ;
		int key = 9; 
		
		System.out.println("Iterative: "+ binarySearchIterative(array, key, low, high)   );
		//--------------------------
		System.out.println("Recursive: "+ binarySearchRecursive(array, key, low, high)   );
		
		
		
	}
	
	/**
	 * Iterative binary search
	 * Runs on O(lg N) 
	 * @param array
	 * 
	 * 
	 * @param key
	 * @param low
	 * @param high
	 * @return index
	 */
	public static int binarySearchIterative(int array[], int key, int low, int high){
	
		boolean found = false;
		int mid = -1;
		
		while(high >= low){
				mid = (low+high)/2;
				if(array[mid] == key){
					found = true;
					break;
				}
				else{
					if(key > array[mid]){
						low = mid + 1;
					}else{
						high = mid - 1;
						
					}
				}
		}
		
		if(found)return mid;
		else return -1;
		
		
	}
	
	
	/**
	 * Recursive Binary Search
	 * Runs on O(lg N) 
	 * @param array
	 * @param key
	 * @param low
	 * @param high
	 * @return index
	 */
	public static int binarySearchRecursive(int array[], int key, int low, int high) {
		if (high < low) {
			return -1;// not found
		}

		int mid = low + (high - low) / 2;
		if (array[mid] > key) {
			return binarySearchRecursive(array, key, low, mid - 1);
		} else if (array[mid] < key) {
			return binarySearchRecursive(array, key, mid + 1, high);
		} else {
			return mid;// found

		}
	}
}
